package chapter16;

/**
 * Created by 蜡笔小新丶 on 2017/10/27.
 */
public class CreatTree<T> {
    BTNode<T> root;
    public CreatTree(){
        root = null;
    }

    public BTNode<T> reConstructBinaryTree(T [] pre,T [] in) {
        BTNode root=new BTNode(pre[0]);//前序的第一个数定为根
        int len=pre.length;
        //当只有一个数的时候
        if(len==1){
            root.left=null;
            root.right=null;
            return root;
        }
        //找到中序中的根位置
        T rootval= (T) root.getElement();
        int i;
        for(i=0;i<len;i++){
            if(root.getElement()==in[i])
                break;
        }
        //创建左子树
        if(i>0){
            T[] pr=(T[])new Object[i];
            T[] ino=(T[])new Object[i];
            for(int j=0;j<i;j++){
                pr[j]=pre[j+1];
            }
            for(int j=0;j<i;j++){
                ino[j]=in[j];
            }
            root.left=reConstructBinaryTree(pr,ino);
        }else{
            root.left=null;
        }
        //创建右子树
        if(len-i-1>0){
            T[] pr=(T[])new Object[len-i-1];
            T[] ino=(T[])new Object[len-i-1];
            for(int j=i+1;j<len;j++){
                ino[j-i-1]=in[j];
                pr[j-i-1]=pre[j];
            }
            root.right=reConstructBinaryTree(pr,ino);
        }else{
            root.right=null;
        }
        return root;
    }
}
